package history.study.tow_pointer;

public class LeetCode_19 {
    // 使用快慢指针，步长都为1，两个指针间距为n
    // 当快指针遍历到尾节点时，删除慢指针的下一个节点
    // 限制：需要注意当删除第一个、最后一个节点以及只有一个节点的场景
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null || n <=0) return head;
        int i=1;
        ListNode listNode = head;
        while (listNode.next!=null) {
            i++;
            listNode = listNode.next;
        }
        if (i == 1) return null;
        if (i == n) {
            head = head.next;
            return head;
        }
        n %= i;
        ListNode fastNode = head;
        ListNode slowNode = head;
        while(n-->0 && fastNode.next!=null) fastNode = fastNode.next;
        while (fastNode.next!=null) {
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        if (n == 1) {
            slowNode.next = null;
        } else {
            slowNode.next = slowNode.next.next;
        }
        return head;
    }
}
